題目連結(https://leetcode.com/problems/symmetric-tree/description/?envType=problem-list-v2&envId=breadth-first-search)

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

今天原本要寫的題目沒寫出來，所以拿以前寫過的DFS/BFS 題目趕緊頂一下><

1. Repeat（題目重複確認）

• 輸入：二元樹的root
• 輸出：true or false
• 前提：
  • 樹必須對稱於根節點
  • 左右子樹結構和節點值完全對稱，包括空節點

2. Examples（舉例確認理解）

Example 1
Input: root = [1,2,2,3,4,4,3]
Output: true
       1
     /   \
    2     2
   / \   / \
  3   4 4   3

Example 2
Input: root = [1,2,2,null,3,null,3]
Output: false

3. Approach（解題思路）

方法 1：遞迴（DFS）

• 檢查左右子樹是否對稱
  1. 如果兩個節點都為空 → 對稱
  2. 如果只有一個節點為空 → 不對稱
  3. 如果兩個節點值不相等 → 不對稱
  4. 遞迴檢查：
     • 左子樹的左節點 vs 右子樹的右節點
     • 左子樹的右節點 vs 右子樹的左節點
• 時間複雜度：O(n) → 每個節點訪問一次
• 空間複雜度：O(h) → 遞迴深度，h 為樹高

方法 2：迭代（BFS / Queue）

• queue 維護左右子樹節點對
• 每次從 queue 取兩個節點，比較值和結構是否對稱
• 適合不想用遞迴，或者擔心 stack overflow 的情況

4. Code（C++）

方法 1：遞迴（DFS）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true; //空樹自動對稱
        return isMirror(root -> left, root -> right);
    }

private:
    bool isMirror(TreeNode* t1, TreeNode* t2){
        if(!t1 && !t2) return true;
        if(!t1 || !t2) return false;

        // 左子樹的左 vs 右子樹的右 AND 左子樹的右 vs 右子樹的左
        return (t1 -> val == t2 -> val)&&
            isMirror(t1 -> left, t2 -> right)&&
            isMirror(t1 -> right, t2 -> left);
    } //三個條件都要成立才會是對稱，所以用&&

};

方法 2：迭代（BFS / Queue）

#include <queue>
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
            if (!root) return true; //空樹自動對稱
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);

        while (!q.empty()) { //queue還沒空時
            TreeNode* t1 = q.front(); q.pop();
            TreeNode* t2 = q.front(); q.pop();

            if (!t1 && !t2) continue;           // 都空，對稱
            if (!t1 || !t2) return false;       // 一空一不空，不對稱
            if (t1->val != t2->val) return false;

            // 注意進入 queue 對稱順序
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        return true;
    }
};

5. Test 範例

6. 相關題目與延伸概念

• 102. Binary Tree Level Order Traversal BFS
• 104. Maximum Depth of Binary Tree 遞迴或 BFS
• 226. Invert Binary Tree 遞迴或迭代
• BFS / DFS 基礎題 → 練習左右子樹對稱概念

7. 補充：語法＆注意事項

• 遞迴函式 isMirror(TreeNode* t1, TreeNode* t2)：
  • t1 和 t2 的順序很重要，左對右，右對左
  • 如果調換順序 isMirror(t2->right, t1->left) 會邏輯不對
• 指標判斷
  • if (!t1 && !t2) → 兩個空指標 → 對稱
  • if (!t1 || !t2) → 一個空 → 不對稱
• 迭代法進入 queue 順序
  • 保持鏡像對稱：t1->left vs t2->right，t1->right vs t2->left
• 空樹的處理
  • if (!root) return true → 空樹自動對稱
• 時間/空間複雜度
  • DFS 遞迴：O(n) / O(h)
  • BFS 迭代：O(n) / O(n)（最壞情況 queue 大小為樹寬度）

ps. 部分內容經 AI 協助整理